/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * <p>二叉树的中序遍历</p>
 * @author towan
 * @email tongwenzide@163.com
 * 2015年5月21日
 */
public class BinaryTreeInorderTraversal {

  public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> result = new ArrayList<Integer>();
      if(root!=null){
          inOrderTraversal(root,result);
      }
      return result;
    }

/**
 * 二叉树的中序遍历迭代遍历
 * @param root
 * @param result
 * @author towan
 * 2015年5月21日
 */
private void inOrderTraversal(TreeNode root, List<Integer> result) {
    if(root!=null){
        inOrderTraversal(root.left,result );
        result.add(root.val);
        inOrderTraversal(root.right,result );
    }
}

public static void main(String[] args) {
    TreeNode t1 = new TreeNode(3);
    TreeNode tleft = new TreeNode(8);
    TreeNode tright = new TreeNode(7);
    t1.left = tleft;
    t1.right = tright;

    tright.left = new TreeNode(3);
    tright.right = new TreeNode(8);

    tleft.left = new TreeNode(9);
    tleft.right = new TreeNode(2);

    BinaryTreeInorderTraversal traversal = new BinaryTreeInorderTraversal();
    List<Integer> list = traversal.inorderTraversal(t1);
    System.out.println(list);
}
}
